W10. Недетерминированные FSA, регулярные выражения, машины Тьюринга и вычислимость

1. Краткое содержание

1.1 Детерминизм и недетерминизм

1.1.1 Детерминированные вычисления

Детерминированный конечный автомат (DFSA) — классическая модель, в которой каждой паре «состояние — входной символ» соответствует ровно одно следующее состояние. Формально DFSA — это 5‑кортеж \(\langle Q, \Sigma, \delta, q_0, F \rangle\), где:

• \(Q\) — конечное множество состояний;
• \(\Sigma\) — конечный входной алфавит;
• \(\delta : Q \times \Sigma \rightarrow Q\) — полная функция переходов: для каждого состояния и каждого входного символа следующее состояние определяется однозначно;
• \(q_0 \in Q\) — начальное состояние;
• \(F \subseteq Q\) — множество принимающих состояний.

Функция переходов \(\delta\) полна: она определена для каждой пары \((q, a) \in Q \times \Sigma\). Значит, DFSA никогда не «застревает» — у него всегда есть ровно один переход, по которому можно продолжить.

1.1.2 Недетерминированные вычисления

Недетерминизм обобщает детерминированную модель, разрешая из одного состояния по одному входному символу иметь ноль, один или несколько возможных переходов. Вместо одного фиксированного пути недетерминированная машина концептуально «исследует» все ветви одновременно.

Недетерминированный конечный автомат (NFSA) (также пишут NDFSA) — это кортеж \(\langle Q, \Sigma, \delta, q_0, F \rangle\), где все компоненты такие же, как у DFSA, кроме:

\[\delta : Q \times \Sigma \rightarrow \mathbb{P}(Q)\]

где \(\mathbb{P}(Q)\) — степенное множество \(Q\), то есть множество всех подмножеств \(Q\). Функция переходов теперь возвращает множество состояний‑преемников (возможно пустое, возможно с более чем одним элементом).

Детерминированные (слева) и недетерминированные (справа) переходы из q₀

Ключевая наглядная идея: недетерминизм моделирует параллельный перебор — машина одновременно развивает все допустимые переходы. В терминах реализации это можно представить как порождение отдельного «потока» для каждого возможного следующего состояния.

1.1.3 Расширенная функция переходов \(\delta^*\)

И для детерминированных, и для недетерминированных автоматов функцию переходов обобщают с одного символа на целые строки.

Для NFSA \(M = \langle Q, \Sigma, \delta, q_0, F \rangle\) расширенная функция переходов \(\delta^* : Q \times \Sigma^* \rightarrow \mathbb{P}(Q)\) задаётся индуктивно:

1. Для каждого \(q \in Q\): \(\delta^*(q, \epsilon) = \{q\}\) — чтение пустой строки оставляет машину в том же состоянии.
2. Для каждого \(q \in Q\), \(y \in \Sigma^*\) и \(i \in \Sigma\): \[\delta^*(q, yi) = \bigcup_{q' \in \delta^*(q, y)} \delta(q', i)\] То есть после чтения \(y\) машина находится в некотором множестве состояний; при чтении ещё одного символа \(i\) к каждому из этих состояний применяют \(\delta\) и объединяют получившиеся множества.

Пример. Пусть \(\delta(q_1, a) = \{q_2, q_3\}\), \(\delta(q_2, b) = \{q_4, q_5\}\), \(\delta(q_3, b) = \{q_5, q_6\}\). Тогда: \[\delta^*(q_1, ab) = \delta(q_2, b) \cup \delta(q_3, b) = \{q_4, q_5\} \cup \{q_5, q_6\} = \{q_4, q_5, q_6\}\]

1.1.4 Условие принятия для NFSA

Строка \(x \in \Sigma^*\) принимается NFSA \(M\) тогда и только тогда, когда среди состояний, достижимых после чтения \(x\), есть хотя бы одно принимающее:

\[x \in L(M) \iff \delta^*(q_0, x) \cap F \neq \emptyset\]

Это называется экзистенциальным недетерминизмом: достаточно, чтобы один вычислительный путь привёл в принимающее состояние. Если хотя бы одна ветвь «успешна», строка принимается.

Существует и универсальная интерпретация (в других контекстах): \(\delta^*(q_0, x) \subseteq F\), то есть все достижимые состояния должны быть принимающими. Стандартный NFSA использует экзистенциальную интерпретацию.

1.1.5 NFSA с \(\epsilon\)-переходами

\(\epsilon\)-NFSA расширяет NFSA, разрешая переходы по пустой строке \(\epsilon\). Функция переходов становится:

\[\delta : Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathbb{P}(Q)\]

\(\epsilon\)-замыкание состояния \(q\) — это множество всех состояний, достижимых из \(q\) только по \(\epsilon\)-переходам (ноль или больше шагов), включая само \(q\):

\[\epsilon\text{-closure}(q) = \{q' \mid q \xrightarrow{\epsilon^*} q'\}\]

Расширенная функция переходов для \(\epsilon\)-NFSA модифицируется так, что после чтения любого «настоящего» символа машина дополнительно проходит все достижимые \(\epsilon\)-переходы:

1. \(\delta^*(q, \epsilon) = \epsilon\text{-closure}(\{q\})\)
2. \(\delta^*(q, yi) = \epsilon\text{-closure}\!\left(\bigcup_{q' \in \delta^*(q, y)} \delta(q', i)\right)\)

\(\epsilon\)-переходы строго не обязательны — любой \(\epsilon\)-NFSA можно преобразовать в эквивалентный NFSA без \(\epsilon\)-переходов — но они часто сильно упрощают конструирование автоматов (в частности, в конструкции Томпсона для регулярных выражений).

1.2 Эквивалентность DFSA и NFSA

Один из фундаментальных фактов теории автоматов: DFSA и NFSA распознают в точности один и тот же класс языков — регулярные языки. Недетерминизм не добавляет выразительности конечным автоматам; он даёт удобство при проектировании.

1.2.1 Алгоритм построения подмножеств

Дан NFSA \(A_{ND} = \langle Q, \Sigma, \delta, q_0, F \rangle\). Эквивалентный DFSA \(A_D = \langle Q_D, \Sigma, \delta_D, q_{0D}, F_D \rangle\) строится так:

• \(Q_D = \mathbb{P}(Q)\) — каждое состояние DFSA соответствует подмножеству состояний NFSA (отсюда название построение подмножеств или построение на степенном множестве).
• \(q_{0D} = \{q_0\}\) — DFSA стартует в одноэлементном множестве, содержащем начальное состояние NFSA.
• \(F_D = \{S \in Q_D \mid S \cap F \neq \emptyset\}\) — состояние DFSA принимающее, если оно содержит хотя бы одно принимающее состояние NFSA.
• \(\delta_D(S, a) = \bigcup_{q \in S} \delta(q, a)\) для каждого \(S \in Q_D\) и \(a \in \Sigma\).

Пошаговая процедура:

1. Построить таблицу переходов NFSA.
2. Создать таблицу DFSA; отметить начальное состояние как \(\{q_0\}\).
3. Для каждого состояния DFSA (это множество состояний NFSA) и каждого входного символа вычислить \(\delta_D\), объединяя переходы NFSA из всех состояний множества.
4. Каждое новое множество из шага 3, которое ещё не встречалось, становится новым состоянием DFSA; повторять шаг 3 для него.
5. Остановиться, когда новых состояний DFSA не появляется.
6. Отметить принимающими все состояния DFSA, содержащие хотя бы одно принимающее состояние NFSA.

Стоимость в худшем случае: если у NFSA \(n\) состояний, у DFSA может потребоваться до \(2^n\) состояний. На практике многие подмножества недостижимы, и фактическое число состояний часто гораздо меньше.

1.2.2 Зачем нужен NFSA, если силы он не добавляет?

Хотя NFSA не распознают «больше» языков, чем DFSA, они полезны по двум причинам:

• Простота конструирования. NFSA для шаблона часто гораздо проще построить. Например, NFSA для строк, содержащих подстроку \(abbaab\), — линейная цепочка из 7 состояний, тогда как эквивалентный DFSA требует аккуратной обработки всех возможных частичных совпадений при «откате».
• Экспоненциальное сжатие состояний. NFSA с \(n\) состояниями может представлять язык, минимальный DFSA для которого требует \(2^n\) состояний. Поэтому NFSA — важное промежуточное представление при построении компиляторов (лексический анализ) и при сопоставлении с образцом.

1.3 Регулярные выражения

Регулярные выражения (RegExp) были введены Стивеном Клини как компактная алгебраическая запись для регулярных языков. Они повсеместно используются в поиске по тексту, компиляторах и формальной верификации.

1.3.1 Синтаксис и индуктивное определение

Регулярное выражение над алфавитом \(\Sigma\) задаётся индуктивно:

Базис:

• \(\emptyset\) — RegExp, обозначающий пустой язык \(L(\emptyset) = \emptyset\).
• \(\epsilon\) — RegExp, обозначающий \(L(\epsilon) = \{\epsilon\}\) — язык, состоящий только из пустой строки.
• Каждый символ \(\sigma \in \Sigma\) — RegExp с \(L(\sigma) = \{\sigma\}\).

Индукция. Если \(r\) и \(s\) — RegExp, то:

• \((r \mid s)\) — RegExp: объединение, \(L(r \mid s) = L(r) \cup L(s)\).
• \((r \cdot s)\) — RegExp (точку часто опускают): конкатенация, \(L(r \cdot s) = \{uv \mid u \in L(r),\, v \in L(s)\}\).
• \(r^*\) — RegExp: звезда Клини, \(L(r^*) = \{x_1 x_2 \cdots x_k \mid k \geq 0,\, x_i \in L(r)\}\).

Дополнительная запись \(r^+ = r \cdot r^*\) означает «один или более повторов»: \(L(r^+) = \{x_1 \cdots x_k \mid k \geq 1,\, x_i \in L(r)\}\).

1.3.2 Приоритет операций

Когда скобки опущены, операции выполняются в таком порядке (от большего приоритета к меньшему):

1. \({}^*\) (звезда Клини)
2. \(\cdot\) (конкатенация)
3. \(\mid\) (объединение)

Поэтому \(\epsilon \mid a^* \cdot b\) разбирается как \(\epsilon \mid ((a)^* \cdot b)\), то есть \(\{\epsilon\} \cup \{a^n b \mid n \geq 0\}\).

1.3.3 Примеры

• \(0 \mid 1 = \{0, 1\}\)
• \(\epsilon \mid a = \{\epsilon, a\}\)
• \(0 \cdot 1 = \{01\}\)
• \((0 \mid 1) \cdot (\epsilon \mid 0) = \{0, 1, 00, 10\}\)
• \(\{0, 1\}^* =\) любая строка над \(\{0, 1\}\)
• \(\{00, 11\}^* = \{\epsilon, 00, 11, 0000, 0011, 1100, 1111, \ldots\}\)
• \((0 \cdot (0 \mid 1)^*) \mid ((0 \mid 1)^* \cdot 0)\) = строки над \(\{0,1\}\), которые начинаются или заканчиваются на 0.

1.4 Конструкция Томпсона: RegExp → NFSA

Конструкция Томпсона — алгоритм, который систематически переводит любое регулярное выражение в \(\epsilon\)-NFSA. Каждому синтаксическому фрагменту RegExp соответствует небольшой стандартный фрагмент NFA.

1.4.1 Базовые случаи

Для одного символа \(x \in \Sigma \cup \{\epsilon\}\): создать два состояния \(q\) (старт) и \(f\) (принимающее) с единственным переходом \(q \xrightarrow{x} f\).

1.4.2 Конкатенация: \(s \cdot t\)

Соединить принимающее состояние \(N(s)\) со стартовым состоянием \(N(t)\) через \(\epsilon\)-переход. Общая машина начинается в старте \(N(s)\) и принимает в принимающем состоянии \(N(t)\).

1.4.3 Объединение: \(s \mid t\)

Создать новое начальное состояние \(q\) и новое принимающее \(f\). Добавить \(\epsilon\)-переходы \(q \xrightarrow{\epsilon} q_s\) и \(q \xrightarrow{\epsilon} q_t\) (к стартам \(N(s)\) и \(N(t)\)), а также \(f_s \xrightarrow{\epsilon} f\) и \(f_t \xrightarrow{\epsilon} f\) (из их принимающих состояний).

1.4.4 Звезда Клини: \(s^*\)

Создать новое начальное \(q\) и новое принимающее \(f\). Добавить:

• \(q \xrightarrow{\epsilon} q_s\) (вход во «внутреннюю» машину),
• \(q \xrightarrow{\epsilon} f\) (обход для нуля повторов),
• \(f_s \xrightarrow{\epsilon} q_s\) (цикл для дополнительных повторов),
• \(f_s \xrightarrow{\epsilon} f\) (выход).

1.4.5 Устранение \(\epsilon\)-переходов (упрощение)

После конструкции Томпсона получившийся NFSA часто содержит избыточные \(\epsilon\)-переходы. Их можно убрать: если у состояния \(q\) есть только \(\epsilon\)-переход в \(q'\), и \(q\) «ничем не выделено», его часто можно слить с \(q'\). Получается меньший и нагляднее NFSA без изменения распознаваемого языка.

1.5 Исторический контекст машин Тьюринга

Машина Тьюринга возникла из глубокого философско-математического кризиса начала XX века.

1.5.1 Principia Mathematica и логицизм

В 1910–1913 годах Бертран Рассел и Альфред Норт Уайтхед опубликовали Principia Mathematica — монументальный труд на ~2000 страниц с попыткой аксиоматизировать всю математику из чисто логических принципов. Проект воплощал логицизм: философский тезис, что математические истины сводимы к чистой логике и выводимы из неё. Авторы утверждали, что их система и полна (всякая математическая истина выводима), и непротиворечива (ложность не выводима).

1.5.2 Теоремы Гёделя о неполноте (1931)

Курт Гёдель разрушил программу логицизма. В 1931 году он доказал теоремы о неполноте: в любой достаточно мощной логической системе существуют утверждения, которые истинны, но не доказуемы внутри этой системы. Ни одна непротиворечивая формальная система, достаточно богатая, чтобы описывать арифметику, не может доказать все арифметические истины. Результат Гёделя показал, что цели Principia Mathematica недостижимы: полнота и непротиворечивость не могут одновременно выполняться для достаточно богатых систем.

1.5.3 Проблема разрешимости Гильберта (1928)

Давид Гильберт, также стремившийся к формализации математики, в 1928 году сформулировал Entscheidungsproblem (нем. проблема разрешимости): существует ли алгоритм, который по любой математической пропозиции и множеству аксиом разрешает, выводима ли эта пропозиция из аксиом? Гильберт называл это «фундаментальной проблемой математической логики» — утвердительный ответ свёл бы всю математику к механическому вычислению.

1.5.4 Отрицательный ответ Чёрча и Тьюринга (1936)

В 1936 году независимо Алонзо Чёрч (через \(\lambda\)-исчисление) и Алан Тьюринг (через свою машинную модель) доказали, что такого общего алгоритма не существует — у проблемы разрешимости отрицательный ответ. Чтобы строго доказать эту невозможность, Тьюрингу нужно было сначала точно определить, что такое алгоритм. Его ответом стала машина Тьюринга.

Ключевая идея Тьюринга — смоделировать механический процесс следования правилам: человек‑математик, по его словам, по сути машина, которая читает символы, хранит конечный объём «состояния» и применяет правила. Формализовав это математическим объектом, он смог доказать точные ограничения.

1.5.5 Тезис Чёрча — Тьюринга

Тезис Чёрча — Тьюринга (не теорема, а широко принятая гипотеза) утверждает:

Любое вычисление, которое может быть выполнено любым реализуемым физическим процессом, может быть выполнено машиной Тьюринга (эквивалентно — выражено в \(\lambda\)-исчислении).

Этот тезис отождествляет неформальное «эффективно вычислимо» с формальным «вычислимо машиной Тьюринга». Он лежит в основе современной теории вычислимости.

1.5.6 Философский вклад Тьюринга

До Тьюринга преобладал идеалистический взгляд: чистым математическим рассуждением разум проникает в платоновскую сферу вечных истин. После Тьюринга распространился материалистический взгляд: машина Тьюринга — модель человека‑математика. Ограничения машины — ограничения математического рассуждения. Математика опирается на то, что допускает физический мир, а не на трансцендентный платоновский мир. Работа Тьюринга означала фундаментальный эпистемологический разрыв в философии математики.

1.6 Машины Тьюринга: устройство и формальное определение

1.6.1 Компоненты машины Тьюринга

Машина Тьюринга (TM) состоит из:

• Входной ленты: последовательность ячеек только для чтения в одном направлении, содержащая входную строку, за которой следуют пустые ячейки.
• Управляющего устройства (конечного управления): хранит текущее состояние \(q\) и задаёт переходы.
• Лент памяти (\(k \geq 0\) лент): ленты чтения/записи с подвижной головкой; в каждой ячейке символ из алфавита памяти \(\Gamma\). Ленты памяти неразрушающие в глобальном смысле — запись в ячейку не стирает другие ячейки.
• Выходной ленты: лента только для записи.

Ключевое отличие от PDA — сохранение памяти: TM может снова прочитать ранее записанные символы памяти, тогда как стек PDA при извлечении уничтожает символы.

1.6.2 Формальное определение

TM с \(k\) лентами памяти — это 7‑кортеж \(T = \langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\), где:

• \(Q\): конечное множество состояний;
• \(I\): входной алфавит (символы на входной ленте);
• \(\Gamma\): алфавит памяти (символы, записываемые на ленты памяти; \(I\) и \(\Gamma\) могут различаться);
• \(\delta\): функция переходов;
• \(q_0 \in Q\): начальное состояние;
• \(Z_0 \in \Gamma\): начальный символ памяти (изначально заполняет каждую ленту памяти — аналог маркера дна стека);
• \(F \subseteq Q\): множество принимающих состояний.

1.6.3 Функция переходов

\[\delta : (Q \setminus F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\})^k \;\rightarrow\; Q \times (\Gamma \cup \{\_\})^k \times \{R, L, S\}^{k+1}\]

Слева направо:

• Область определения: машина в непринимающем состоянии, прочитала один символ с входной ленты и по одному символу с каждой из \(k\) лент памяти.
• Область значений: машина переходит в новое состояние, записывает новый символ на каждую ленту памяти и двигает все \(k+1\) головок (одна входная плюс \(k\) памяти).

Три направления движения головки:

• \(R\) — вправо
• \(L\) — влево
• \(S\) — остаться на месте

Переход изображают как рёбро \(q \to q'\) с подписью: \[i,\; \langle A_1, \ldots, A_k \rangle \;\Big|\; \langle A'_1, \ldots, A'_k \rangle,\; \langle M_0, M_1, \ldots, M_k \rangle\] где \(i\) — прочитанный входной символ, \(A_j\) — символ, прочитанный с \(j\)-й ленты памяти, \(A'_j\) — записываемый на \(j\)-ю ленту, \(M_0\) — направление входной головки, \(M_j\) — направление головки \(j\)-й ленты памяти.

1.7 Примеры машин Тьюринга

1.7.1 Распознавание \(a^n b^n c^n\)

Язык \(L = \{a^n b^n c^n \mid n > 0\}\) не распознаётся ни одним PDA (стек разрушителен: сосчитав \(a\) для согласования с \(b\), мы «теряем» счёт и не можем проверить \(c\)). TM решает задачу с помощью ленты памяти:

1. Читать каждый \(a\) с входа и записывать на ленту памяти символ \(M\) (хранить \(n\) маркеров).
2. Когда все \(a\) прочитаны, двигаться влево по ленте памяти и начать читать \(b\). Для каждого \(b\) «поглощать» один \(M\) с памяти (двигаться влево).
3. Когда все \(n\) символов \(M\) поглощены (достигнут \(Z_0\)) и на входе появляется \(c\), двигаться вправо по памяти и читать \(c\), поглощая по одному \(M\) на каждый \(c\).
4. Принять, когда и вход, и лента памяти одновременно полностью «исчерпаны».

Это работает, потому что лента памяти персистентна — маркеры \(M\) остаются, пока явно не будут пройдены, так что число \(a\) доступно и для проверки \(b\), и для проверки \(c\).

1.7.2 Распознавание \(a^n b^{2n} a^n\)

Для \(L = \{a^n b^{2n} a^n \mid n \geq 1\}\):

1. На каждый прочитанный \(a\) записывать на ленту памяти два символа \(A\) (всего \(2n\) символов \(A\)).
2. Читать \(b\) с входа, двигаясь по памяти влево и поглощая по одному \(A\) на каждый \(b\), проверяя \(2n\) символов \(b\).
3. Читать финальные \(n\) символов \(a\), поглощая \(A\) при движении вправо по памяти (вторая «волна» для хвостовых \(a\)).
4. Принять, когда обе ленты одновременно исчерпаны.

1.7.3 Распознавание \(a^n b^n \cup a^n b^{2n}\)

TM хранит \(n\) символов \(A\), затем считает первые \(n\) символов \(b\). В этот момент либо (a) обнаруживается конец входа — принимаем (случай \(a^n b^n\)), либо (b) есть ещё \(b\) — тогда снова обходим память, считая ещё \(n\) символов \(b\) (случай \(a^n b^{2n}\)), после чего принимаем при одновременном исчерпании входа и памяти.

1.8 Варианты машин Тьюринга и их эквивалентность

1.8.1 Одноленточная TM

Одноленточная TM использует одну ленту для входа, памяти и выхода. Лента неограниченна в обе стороны. Несмотря на это ограничение, одноленточная TM эквивалентна по выразительности многоленточной: любую многоленточную TM можно симулировать одноленточной. Симуляция кодирует все ленты на одной с разделителями и отслеживает позиции головок. Замедление может быть полиномиальным или квадратичным, но класс вычислимых задач не меняется.

1.8.2 Многомерная лента

2D‑лента (или \(d\)-мерная TM) использует сетку вместо линии, головка двигается в до \(2d\) направлений. И такие модели эквивалентны стандартной TM.

1.8.3 Универсальная эквивалентность

Все «разумные» варианты TM (одна лента, несколько лент, многомерная лента, недетерминированная TM и т.д.) распознают один и тот же класс языков — рекурсивно перечислимые языки. Эта устойчивость — аргумент в пользу того, что TM захватывает правильное понятие вычисления, как в тезисе Чёрча — Тьюринга.

1.9 Свойства замкнутости для машин Тьюринга

Класс рекурсивно перечислимых языков (языков, распознаваемых TM) замкнут относительно:

• Объединения: по TM \(M_1\) и \(M_2\) строим TM, которая симулирует обе «параллельно»; принимаем, если принимает хотя бы одна.
• Пересечения: симулируем последовательно; принимаем только если обе принимают.
• Конкатенации: недетерминированно угадываем место разреза; запускаем \(M_1\) на первой части и \(M_2\) на второй.
• Звезды Клини: недетерминированно угадываем разбиение на блоки; проверяем каждый блок.

Для объединения и пересечения наглядно: TM легко симулирует две другие TM последовательно или параллельно.

Не замкнуты относительно дополнения. TM не замкнуты относительно дополнения. Причина: TM, не принимающая строку, может либо отвергнуть её (остановиться в непринимающем), либо зациклиться. Перестановка принимающих и непринимающих останавливающихся состояний работает для TM без циклов, но не устраняет незавершающиеся вычисления.

TM без циклов (всегда останавливающиеся) замкнуты относительно дополнения: для TM, гарантированно останавливающихся на всех входах (рекурсивные или разрешимые), обмен принимающих и отвергающих состояний даёт TM для дополненного языка. Это класс рекурсивных языков (строгое подмножество рекурсивно перечислимых).

1.10 Иерархия языков

Следующая диаграмма суммирует иерархию Хомского в объёме курса:

Полная иерархия языков (Хомский) и соответствующие модели машин

Ключевые наблюдения:

• Регулярные языки (распознаются FSA): только фиксированная конечная память — нет «общего» счёта до \(n\).
• Детерминированные КС‑языки (DPDA): память стека, но переходы детерминированы.
• Контекстно-свободные языки (недетерминированный PDA): стек разрушителен; нельзя одновременно считать несколько независимых величин.
• Рекурсивные (разрешимые) языки: TM всегда останавливаются; замкнуты относительно дополнения.
• Рекурсивно перечислимые языки: TM могут зацикливаться; относительно дополнения не замкнуты.
• Не распознаваемые TM: языки, для которых не существует распознающей TM.

Разницу между рекурсивными и рекурсивно перечислимыми можно проиллюстрировать на C‑программах:

• Множество C‑программ, которые никогда не попадают в бесконечный цикл (ни на каком входе), — рекурсивно.
• Множество C‑программ, которые содержат бесконечный цикл (хотя бы на одном входе), — рекурсивно перечислимо, но не рекурсивно — это связано с проблемой остановки.

1.11 Взгляд через модель памяти

Выбор модели памяти определяет выразительную силу вычислительной модели:

• FSA — фиксированная конечная память: единственная «память» — текущее состояние. Можно «считать» только до числа состояний. Нет произвольной переменной \(n\).
• PDA — расширяемая, но разрушительная память (стек): можно считать до переменной \(n\), но после извлечения символ со стека исчезает. Нельзя одновременно проверить два независимых счётных ограничения.
• TM — персистентная память (лента): записанные символы остаются и доступны для повторного чтения. Поведение близко к архитектуре фон Неймана (произвольный доступ, постоянная память). Можно обрабатывать любой вычислимый язык.

1.12 Мощность множеств и неразрешимость (спойлеры)

Важный мета‑факт объясняет, почему существуют неразрешимые задачи:

• Множество всех программ (на любом фиксированном языке программирования) счётно — программы можно перечислить в лексикографическом порядке.
• Множество всех задач (функций \(\mathbb{N} \to \mathbb{N}\), или, эквивалентно, подмножеств \(\mathbb{N}\)) несчётно (диагональный аргумент Кантора).

Следовательно, задач бесконечно больше, чем программ. «Большинство» задач — в теоретико‑множественном смысле — не имеют алгоритма. Однако естественные, хорошо структурированные задачи часто разрешимы. Самая известная неразрешимая задача — проблема остановки: по программе \(P\) и входу \(x\), останавливается ли \(P\) на \(x\)? Тьюринг доказал, что ни одна TM не может разрешить это для всех пар \((P, x)\).

---

2. Определения

• DFSA (детерминированный конечный автомат): 5‑кортеж \(\langle Q, \Sigma, \delta, q_0, F \rangle\) с полной функцией переходов \(\delta : Q \times \Sigma \to Q\); каждая пара «состояние — вход» ведёт ровно в одно следующее состояние.
• NFSA (недетерминированный конечный автомат): 5‑кортеж \(\langle Q, \Sigma, \delta, q_0, F \rangle\) с \(\delta : Q \times \Sigma \to \mathbb{P}(Q)\); из пары «состояние — вход» может быть ноль, одно или много следующих состояний.
• \(\epsilon\)-NFSA: NFSA, у которого функция переходов допускает \(\epsilon\)-переходы: \(\delta : Q \times (\Sigma \cup \{\epsilon\}) \to \mathbb{P}(Q)\).
• \(\epsilon\)-замыкание: для состояния \(q\) множество \(\epsilon\text{-closure}(q)\) — все состояния, достижимые из \(q\) только по \(\epsilon\)-переходам (включая \(q\)).
• Расширенная функция переходов \(\delta^*\): для NFSA \(\delta^* : Q \times \Sigma^* \to \mathbb{P}(Q)\) — индуктивное расширение \(\delta\) на строки; \(\delta^*(q, \epsilon) = \{q\}\) и \(\delta^*(q, yi) = \bigcup_{q' \in \delta^*(q, y)} \delta(q', i)\).
• Принятие (NFSA): строка \(x\) принимается тогда и только тогда, когда \(\delta^*(q_0, x) \cap F \neq \emptyset\) (экзистенциальный недетерминизм).
• Степенное множество \(\mathbb{P}(Q)\): множество всех подмножеств \(Q\), включая \(\emptyset\) и \(Q\).
• Построение подмножеств: алгоритм перевода NFSA в DFSA, где подмножества состояний NFSA становятся отдельными состояниями DFSA; в худшем случае \(Q_D = \mathbb{P}(Q)\).
• Регулярное выражение (RegExp): формула из \(\emptyset\), \(\epsilon\), символов алфавита, объединения (\(r \mid s\)), конкатенации (\(r \cdot s\)) и звезды Клини (\(r^*\)); обозначает регулярный язык.
• Звезда Клини (\(r^*\)): множество всех строк, полученных конкатенацией нуля или более строк из \(L(r)\).
• Конструкция Томпсона: алгоритм перевода RegExp в \(\epsilon\)-NFSA структурной индукцией по RegExp.
• Логицизм: философия математики: математические истины выводимы из чисто логических принципов (Principia Mathematica).
• Теоремы Гёделя о неполноте: в любой достаточно мощной непротиворечивой формальной системе существуют истинные, но недоказуемые внутри системы утверждения (1931).
• Entscheidungsproblem: вопрос Гильберта (1928) об алгоритме, разрешающем выводимость произвольной математической пропозиции из данных аксиом.
• Тезис Чёрча — Тьюринга: гипотеза, что всякая эффективно вычислимая функция вычислима машиной Тьюринга.
• Машина Тьюринга (TM): 7‑кортеж \(\langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\) — состояния, входной алфавит, алфавит памяти, функция переходов, начальное состояние, начальный символ памяти, принимающие состояния; использует персистентные ленты чтения/записи.
• Рекурсивно перечислимый язык: язык, распознаваемый некоторой TM (на отвергнутых входах TM может не останавливаться).
• Рекурсивный (разрешимый) язык: язык, распознаваемый TM, останавливающейся на всех входах; замкнут относительно дополнения.
• Проблема остановки: разрешить, останавливается ли программа \(P\) на входе \(x\); Тьюринг доказал неразрешимость для всех \((P, x)\).
• Экзистенциальный недетерминизм: критерий принятия: хотя бы один вычислительный путь принимает.
• Универсальный недетерминизм: критерий принятия: все пути принимают.

---

3. Формулы

• Функция переходов DFSA: \(\delta : Q \times \Sigma \rightarrow Q\)
• Функция переходов NFSA: \(\delta : Q \times \Sigma \rightarrow \mathbb{P}(Q)\)
• Функция переходов \(\epsilon\)-NFSA: \(\delta : Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathbb{P}(Q)\)
• Расширенный переход (NFSA, база): \(\delta^*(q, \epsilon) = \{q\}\)
• Расширенный переход (NFSA, шаг): \(\delta^*(q, yi) = \displaystyle\bigcup_{q' \in \delta^*(q,\,y)} \delta(q', i)\)
• Принятие NFSA: \(x \in L(M) \iff \delta^*(q_0, x) \cap F \neq \emptyset\)
• Построение подмножеств — переход DFSA: \(\delta_D(S, a) = \displaystyle\bigcup_{q \in S} \delta(q, a)\)
• Построение подмножеств — принимающие состояния: \(F_D = \{S \in \mathbb{P}(Q) \mid S \cap F \neq \emptyset\}\)
• Функция переходов TM (\(k\) лент): \(\delta : (Q \setminus F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\})^k \rightarrow Q \times (\Gamma \cup \{\_\})^k \times \{R, L, S\}^{k+1}\)

---

4. Примеры

4.1. Построить NFSA для трёх языков (Лаба 9, Задание 1)

Постройте NFSA, распознающие следующие языки:

1. \(L_a = \{x \in \{0, 1\}^* \mid x \text{ оканчивается на } 101\}\)

2. \(L_b = \{xy \mid x \in \{a\}^* \land y \in \{a, b\}^* \land y \text{ не начинается с } b \land \text{каждый } a \text{ в } y \text{ сопровождается ровно одним } b\}\)

3. \(L_c = \{x \in \{a, b, c\}^* \mid x \text{ оканчивается на } ab,\; bc \text{ или } ca\}\)

Показать решение

(a) \(L_a\): строки, оканчивающиеся на \(101\).

Используем стандартный приём «угадывания суффикса»: NFSA «угадывает», где начинается финальная подстрока \(101\), и затем детерминированно проверяет её.

• \(q_0\): старт, петли на \(0, 1\); переход в \(q_1\) по \(1\) (гипотеза: финальная \(101\) начинается здесь).
• \(q_1\): переход в \(q_2\) по \(0\).
• \(q_2\): переход в \(q_3\) по \(1\).
• \(q_3\): принимающее состояние (исходящие переходы не нужны).

(b) \(L_b\): строки вида \(a^* \cdot y\), где \(y\) не начинается с \(b\), и каждый \(a\) в \(y\) сопровождается ровно одним \(b\).

Язык — (возможно пустой) блок символов \(a\), затем шаблон, где каждому \(a\) соответствует ровно один \(b\) (и в начале \(y\) нет ведущего \(b\)).

• \(q_0\) (принимающее): петля на \(a\); переход в \(q_1\) по \(a\) (вход в часть \(y\), где после \(a\) обязан следовать \(b\)).
• \(q_1\): переход в \(q_2\) (принимающее) по \(b\).
• \(q_2\) (принимающее): переход в \(q_1\) по \(a\) (каждый новый \(a\) в \(y\) снова требует \(b\)).

(c) \(L_c\): строки, оканчивающиеся на \(ab\), \(bc\) или \(ca\).

Три параллельные ветви детектора суффикса длины два:

• \(q_0\): петли на \(a, b, c\); переходы в \(q_1\) по \(a\), в \(q_2\) по \(b\), в \(q_3\) по \(c\).
• \(q_1\): переход в \(q_4\) (принимающее) по \(b\) (обнаружено \(ab\)).
• \(q_2\): переход в \(q_4\) (принимающее) по \(c\) (обнаружено \(bc\)).
• \(q_3\): переход в \(q_4\) (принимающее) по \(a\) (обнаружено \(ca\)).
• \(q_4\): одно общее принимающее состояние.

Ответ: три простых NFSA по шаблону «угадывания суффикса».

4.2. Перевести NFSA в DFSA: язык, оканчивающийся на 101 (Лаба 9, Задание 2)

NFSA для \(L_1 = \{x \in \{0, 1\}^* \mid x \text{ оканчивается на } 101\}\) имеет четыре состояния: старт \(q_0\) с петлёй на \(0, 1\); переходы \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_3\) (принимающее).

Примените алгоритм построения подмножеств, чтобы получить эквивалентный DFSA. Выпишите полную таблицу переходов DFSA и укажите все принимающие состояния.

Показать решение

Таблица переходов NFSA:

\(q\)	\(\delta(q, 0)\)	\(\delta(q, 1)\)
\(\rightarrow q_0\)	\(\{q_0\}\)	\(\{q_0, q_1\}\)
\(q_1\)	\(\{q_2\}\)	\(\emptyset\)
\(q_2\)	\(\emptyset\)	\(\{q_3\}\)
\(*q_3\)	\(\emptyset\)	\(\emptyset\)

Построение подмножеств:

Старт: \(D_0 = \{q_0\}\).

Состояние DFSA	по \(0\)	по \(1\)
\(\rightarrow \{q_0\}\)	\(\{q_0\}\)	\(\{q_0, q_1\}\)
\(\{q_0, q_1\}\)	\(\{q_0, q_2\}\)	\(\{q_0, q_1\}\)
\(\{q_0, q_2\}\)	\(\{q_0\}\)	\(\{q_0, q_1, q_3\}\)
\(*\{q_0, q_1, q_3\}\)	\(\{q_0, q_2\}\)	\(\{q_0, q_1\}\)

У DFSA 4 состояния. Единственное принимающее — \(\{q_0, q_1, q_3\}\) (содержит \(q_3 \in F\)).

Проверка: из \(\{q_0\}\) при чтении \(101\): \(\{q_0\} \xrightarrow{1} \{q_0,q_1\} \xrightarrow{0} \{q_0,q_2\} \xrightarrow{1} \{q_0,q_1,q_3\}\) ✓ (принимающее).

Ответ: DFSA из 4 состояний с принимающим \(\{q_0, q_1, q_3\}\).

4.3. Перевести NFSA в DFSA: ограниченный язык над \(\{a, b\}\) (Лаба 9, Задание 3)

NFSA для \(L_2\) имеет три состояния: \(q_0\) (принимающее) с петлёй на \(a\) и переходом в \(q_1\) по \(a\); из \(q_1\) переход в \(q_2\) (принимающее) по \(b\); из \(q_2\) возврат в \(q_1\) по \(a\).

Примените построение подмножеств к этому NFSA и получите эквивалентный DFSA.

Показать решение

Таблица переходов NFSA (принимающие: \(q_0, q_2\)):

\(q\)	\(\delta(q, a)\)	\(\delta(q, b)\)
\(*q_0\)	\(\{q_0, q_1\}\)	\(\emptyset\)
\(q_1\)	\(\emptyset\)	\(\{q_2\}\)
\(*q_2\)	\(\{q_1\}\)	\(\emptyset\)

Построение подмножеств:

Старт: \(\{q_0\}\) (принимающее, так как \(q_0 \in F\)).

Состояние DFSA	по \(a\)	по \(b\)
\(*\{q_0\}\)	\(\{q_0, q_1\}\)	\(\emptyset\)
\(*\{q_0, q_1\}\)	\(\{q_0, q_1\}\)	\(\{q_2\}\)
\(\emptyset\)	\(\emptyset\)	\(\emptyset\)
\(*\{q_2\}\)	\(\{q_1\}\)	\(\emptyset\)
\(\{q_1\}\)	\(\emptyset\)	\(\{q_2\}\)

Принимающие состояния DFSA: \(\{q_0\}\), \(\{q_0, q_1\}\), \(\{q_2\}\) (каждое содержит хотя бы одно из \(q_0, q_2\)).

Ответ: DFSA из 5 состояний. Состояние‑сток \(\emptyset\) отсекает отвергаемые префиксы (например, строки, начинающиеся с \(b\)).

4.4. Перевести NFSA в DFSA: строки, оканчивающиеся на \(ab\), \(bc\) или \(ca\) (Лаба 9, Задание 4)

NFSA для \(L_3 = \{x \in \{a, b, c\}^* \mid x \text{ оканчивается на } ab,\; bc \text{ или } ca\}\) — тот же, что в пункте (c) задания 4.1. Примените построение подмножеств и выпишите полную таблицу переходов DFSA.

Показать решение

NFSA (из задания 4.1(c)): \(Q = \{q_0, q_1, q_2, q_3, q_4\}\), принимающие: \(\{q_4\}\).

\(q\)	\(\delta(q, a)\)	\(\delta(q, b)\)	\(\delta(q, c)\)
\(\rightarrow q_0\)	\(\{q_0, q_1\}\)	\(\{q_0, q_2\}\)	\(\{q_0, q_3\}\)
\(q_1\)	\(\emptyset\)	\(\{q_4\}\)	\(\emptyset\)
\(q_2\)	\(\emptyset\)	\(\emptyset\)	\(\{q_4\}\)
\(q_3\)	\(\{q_4\}\)	\(\emptyset\)	\(\emptyset\)
\(*q_4\)	\(\emptyset\)	\(\emptyset\)	\(\emptyset\)

Построение подмножеств (только достижимые состояния):

Старт: \(\{q_0\}\).

Состояние DFSA	по \(a\)	по \(b\)	по \(c\)
\(\rightarrow\{q_0\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2\}\)	\(\{q_0,q_3\}\)
\(\{q_0,q_1\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2,q_4\}\)	\(\{q_0,q_3\}\)
\(\{q_0,q_2\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2\}\)	\(\{q_0,q_3,q_4\}\)
\(\{q_0,q_3\}\)	\(\{q_0,q_1,q_4\}\)	\(\{q_0,q_2\}\)	\(\{q_0,q_3\}\)
\(*\{q_0,q_2,q_4\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2\}\)	\(\{q_0,q_3,q_4\}\)
\(*\{q_0,q_3,q_4\}\)	\(\{q_0,q_1,q_4\}\)	\(\{q_0,q_2\}\)	\(\{q_0,q_3\}\)
\(*\{q_0,q_1,q_4\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2,q_4\}\)	\(\{q_0,q_3\}\)

Принимающие состояния DFSA: содержащие \(q_4\).

Ответ: DFSA из 7 состояний. Принимающие: \(\{q_0,q_2,q_4\}\), \(\{q_0,q_3,q_4\}\) и \(\{q_0,q_1,q_4\}\).

4.5. Описать языки регулярных выражений (Лаба 9, Задание 5)

Над \(\Sigma = \{0, 1\}\) дайте краткое описание на русском языке каждого из языков:

1. \(\emptyset\)
2. \(\emptyset^*\)
3. \((0^* 1^*)^* 000 (0 \mid 1)^*\)
4. \((1 \mid \epsilon)(00^* 1)^* 0^*\)

Показать решение

1. \(\emptyset\): пустой язык — не принимается ни одна строка, в том числе пустая.
2. \(\emptyset^*\): язык, состоящий только из пустой строки \(\{\epsilon\}\). Звезда Клини от пустого множества допускает ноль повторов «ничего», что даёт ровно \(\epsilon\).
3. \((0^* 1^*)^* 000 (0 \mid 1)^*\): все двоичные строки, содержащие подстроку \(000\). Префикс \((0^*1^*)^*\) порождает \(\{0,1\}^*\); затем обязательно идёт блок из трёх нулей; суффикс \((0 \mid 1)^*\) — произвольный. Итого \(\{x \in \{0,1\}^* \mid x \text{ contains } 000 \text{ as a substring}\}\).
4. \((1 \mid \epsilon)(00^* 1)^* 0^*\): строки, в которых каждая единица непосредственно предшествует хотя бы одному нулю (нет ведущей \(1\) без предшествующего \(0\), кроме случая опциональной самой первой \(1\), задаваемой вариантом \(1 \mid \epsilon\)). Точнее: опциональная ведущая \(1\), затем ноль или более блоков вида \(00^*1\) (один или более нулей и затем единица), затем ноль или более завершающих нулей. Это множество двоичных строк, в которых \(1\) никогда не встречается без предшествующего \(0\), кроме, возможно, самого первого символа.

Ответ: (1) пустой язык; (2) \(\{\epsilon\}\); (3) строки, содержащие \(000\); (4) строки, где каждая \(1\) (кроме, возможно, первого символа) предваряется хотя бы одним \(0\).

4.6. Построить регулярные выражения над \(\{a, b\}\) (Лаба 9, Задание 6)

Постройте регулярные выражения над \(\Sigma = \{a, b\}\) для языков:

5. Множество строк из чередующихся символов \(a\) и \(b\).
6. Множество строк с нечётным числом символов \(a\).
7. Множество строк, оканчивающихся на \(b\) и не содержащих подстроки \(aa\).
8. Множество строк, в которых и число \(a\), и число \(b\) чётны.

Показать решение

5. Чередование \(a\) и \(b\).

Чередующиеся строки начинаются с \(a\) или с \(b\) и строго чередуются. Возможны четыре «формы»: \(\epsilon\), \(a\), \(b\) и бесконечные семейства, начинающиеся с \(a\) или \(b\):

\[(\epsilon \mid a)(ba)^* (\epsilon \mid b)\]

Раскрытие: строка пуста, либо начинается с опционального \(a\), затем ноль или более пар \(ba\), затем опциональный хвостовой \(b\). Порождаются все чередующиеся строки: \(\epsilon, a, b, ab, ba, aba, bab, abab, baba, \ldots\)

6. Нечётное число символов \(a\).

Отслеживаем чётность числа \(a\). Между группами \(b\) вставлены \(a\). После чётного числа \(a\) нужна ещё одна \(a\), затем можно добавлять пары с сохранением чётности:

\[b^* (a b^* a b^*)^* a b^*\]

Чтение: произвольное число \(b\), затем ноль или более пар \(a\) (каждая пара сохраняет чётное число \(a\)) с возможными \(b\) между ними, затем ровно одна \(a\) (делает общее число \(a\) нечётным), затем хвостовые \(b\).

7. Строки, оканчивающиеся на \(b\), без подстроки \(aa\).

Так как \(aa\) запрещено, после каждого \(a\) сразу должен идти \(b\) (строка оканчивается на \(b\), поэтому у каждого \(a\) есть следующий \(b\)). Шаблон: блоки \(b\), чередующиеся с парами \(ab\):

\[(b \mid ab)^*\]

Порождаются все строки над \(\{a, b\}\), где после каждого \(a\) сразу идёт \(b\). Такие строки оканчиваются на \(b\) (последний символ из \(b\) или из \(ab\) — в обоих случаях \(b\)) и не содержат \(aa\).

8. Чётное число \(a\) и чётное число \(b\).

Нужно отслеживать чётность обоих счётчиков. Четыре «режима»: (чёт-\(a\), чёт-\(b\)), (неч-\(a\), чёт-\(b\)), (чёт-\(a\), неч-\(b\)), (неч-\(a\), неч-\(b\)). Нужны строки, начинающиеся и заканчивающиеся в (чёт, чёт).

Регулярное выражение:

\[(aa \mid bb \mid (ab \mid ba)(aa \mid bb)^*(ab \mid ba))^*\]

Интерпретация: собираем строку из блоков, сохраняющих чётность по обоим счётчикам. Блок — либо \(aa\) (+2 к \(a\)), либо \(bb\) (+2 к \(b\)), либо пара «перекрёстных» ходов \((ab \mid ba)\), разделённых опциональными чётными блоками — в сумме по одному \(a\) и одному \(b\), обе чётности остаются чётными.

Ответ: (5) \((\epsilon \mid a)(ba)^*(\epsilon \mid b)\); (6) \(b^*(ab^*ab^*)^*ab^*\); (7) \((b \mid ab)^*\); (8) \((aa \mid bb \mid (ab \mid ba)(aa \mid bb)^*(ab \mid ba))^*\).

4.7. Построить NFSA для языков из домашнего задания (Лаба 9, Задание 7)

Постройте NFSA над \(\Sigma_1 = \{a, b\}\) и \(\Sigma_2 = \{0, 1\}\) для каждого языка ниже, затем переведите каждый в DFSA.

1. \(L_0 = \{x \in \Sigma_2^* \mid \text{после каждого } 0 \text{ в } x \text{ следует хотя бы один } 1\}\). Примеры строк: \(010111\), \(1111\), \(01110111011\).
2. \(L_1 = \{x \in \Sigma_1^* \mid x \text{ содержит подстроку } abbaab\}\)
3. \(L_2 = \{x \in \Sigma_1^* \mid |x| \geq 2 \land \text{два последних символа } x \text{ совпадают}\}\)
4. \(L_3 = \{x \in \Sigma_2^* \mid x \text{ содержит ровно пять символов } 0\}\)

Показать решение

\(L_0\): после каждого \(0\) следует хотя бы один \(1\).

NFSA. Отвергаем строки, где \(0\) стоит в самом конце или сразу за ним идёт другой \(0\) без промежуточной \(1\).

• \(q_0\) (принимающее, старт): петля на \(1\); переход в \(q_1\) по \(0\).
• \(q_1\): переход в \(q_0\) по \(1\) (обязательная \(1\) после \(0\)); переход в \(q_2\) (мёртвое/отвергающее) по \(0\) (\(0\) сразу после другого \(0\) без промежуточной \(1\)).
• \(q_2\) (мёртвое): петли на \(0, 1\).

Перевод в DFSA. NFSA почти детерминирован; DFSA совпадает по структуре; \(q_2\) — явное стоковое состояние. «Живые» состояния — \(q_0\) и \(q_1\). Пустая строка принимается (старт принимающий).

\(L_1\): содержит подстроку \(abbaab\).

NFSA. Линейная цепочка, выписывающая \(abbaab\), с петлёй в старте:

• \(q_0\): петли на \(a, b\); переход в \(q_1\) по \(a\).
• \(q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_3 \xrightarrow{a} q_4 \xrightarrow{a} q_5 \xrightarrow{b} q_6\).
• \(q_6\) (принимающее): петли на \(a, b\).

Перевод в DFSA. Применяем построение подмножеств. В худшем случае до \(2^7 = 128\) состояний, но из‑за структуры «функции отказа» (аналогично KMP) большинство состояний схлопывается. На практике DFSA имеет 8 состояний, соответствующих длинам наибольшего собственного суффикса \(abbaab\), который одновременно является её префиксом.

\(L_2\): \(|x| \geq 2\) и последние два символа совпадают.

NFSA. Машина угадывает, где начинается предпоследний символ:

• \(q_0\): петли на \(a, b\); переход в \(q_1\) по \(a\); в \(q_2\) по \(b\).
• \(q_1\): переход в \(q_3\) (принимающее) по \(a\) (последние два — \(aa\)).
• \(q_2\): переход в \(q_3\) (принимающее) по \(b\) (последние два — \(bb\)).
• \(q_3\): принимающее (исходящих нет — совпадение завершено).

Перевод в DFSA. Построение подмножеств из \(\{q_0\}\):

Состояние DFSA	по \(a\)	по \(b\)
\(\rightarrow\{q_0\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2\}\)
\(\{q_0,q_1\}\)	\(\{q_0,q_1,q_3\}\)	\(\{q_0,q_2\}\)
\(\{q_0,q_2\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2,q_3\}\)
\(*\{q_0,q_1,q_3\}\)	\(\{q_0,q_1,q_3\}\)	\(\{q_0,q_2\}\)
\(*\{q_0,q_2,q_3\}\)	\(\{q_0,q_1\}\)	\(\{q_0,q_2,q_3\}\)

\(L_3\): ровно пять нулей.

NFSA. Считаем нули состояниями \(q_0,\ldots,q_5\), у каждого петля на \(1\), переход по \(0\) к следующему. После \(q_5\) (принимающее) любой дополнительный \(0\) ведёт в отказ:

• \(q_i\) для \(i = 0, \ldots, 4\): петля на \(1\); переход в \(q_{i+1}\) по \(0\).
• \(q_5\) (принимающее): петля на \(1\); переход в \(q_6\) (мёртвое) по \(0\).
• \(q_6\) (мёртвое): петли на \(0, 1\).

Перевод в DFSA. Этот NFSA уже детерминирован — функция переходов однозначна. DFSA совпадает с NFSA (7 состояний: \(q_0\)–\(q_5\) активные, \(q_6\) сток).

Ответ: NFSA и DFSA, как описано выше, для каждого из четырёх языков.

4.8. Доказать замкнутость языков NFSA относительно дополнения (Лекция 9, Задание 1)

Замкнут ли класс языков, распознаваемых NFSA, относительно дополнения? Дайте формальное доказательство.

Показать решение

Утверждение: да, класс языков, распознаваемых NFSA, замкнут относительно дополнения.

Доказательство.

Пусть \(L\) распознаётся некоторым NFSA \(N\). Покажем, что \(\overline{L} = \Sigma^* \setminus L\) также распознаётся некоторым конечным автоматом.

Шаг 1 — перевод NFSA в DFSA.

По теореме о построении подмножеств каждый NFSA эквивалентен некоторому DFSA \(D\), распознающему тот же язык \(L\). То есть \(L(N) = L(D) = L\).

Шаг 2 — дополнение DFSA.

Дан полный (тотальный) DFSA \(D = \langle Q_D, \Sigma, \delta_D, q_{0D}, F_D \rangle\). Построим DFSA \(D' = \langle Q_D, \Sigma, \delta_D, q_{0D}, Q_D \setminus F_D \rangle\), поменяв местами принимающие и непринимающие состояния. Так как \(D\) тотален (из каждого состояния есть переход по каждому символу), \(D'\) — корректный полный DFSA.

Шаг 3 — проверка корректности.

Для любой строки \(x \in \Sigma^*\):

• \(D\) принимает \(x\) тогда и только тогда, когда \(\delta_D^*(q_{0D}, x) \in F_D\).
• \(D'\) принимает \(x\) тогда и только тогда, когда \(\delta_D^*(q_{0D}, x) \in Q_D \setminus F_D\), т.е. \(\delta_D^*(q_{0D}, x) \notin F_D\).

Следовательно, \(D'\) принимает в точности те строки, которые \(D\) отвергает: \[L(D') = \Sigma^* \setminus L(D) = \overline{L}.\]

Так как \(D'\) — DFSA (в частности, частный случай NFSA), \(\overline{L}\) распознаётся NFSA.

Заключение. Класс языков, распознаваемых NFSA (= регулярные языки), замкнут относительно дополнения. \(\square\)

Почему этот приём напрямую не работает для NFSA. Трюк с дополнением (поменять \(F\) и \(Q \setminus F\)) не применим напрямую к NFSA, потому что NFSA принимает, если какая‑то ветвь принимает. Поменяв принимающие состояния, получили бы машину, которая отвергает, если какая‑то ветвь отвергает — то есть принимает только если все ветви принимают (универсальный недетерминизм), что другая семантика. Корректность аргумента критически опирается на предварительный переход к детерминированной конструкции.

4.9. Пояснить, почему для \(a^nb^nc^n\) нужна машина Тьюринга (Лекция 9, Пример 1)

Объясните, почему язык \(L = \{a^n b^n c^n \mid n > 0\}\) не распознаётся ни одним PDA, и опишите решение на машине Тьюринга.

Показать решение

Почему не подходит PDA. PDA распознаёт \(a^n b^n\), помещая в стек по символу на каждый \(a\) и извлекая по одному на каждый \(b\). Но после согласования всех \(b\) стек пуст — счётчик \(n\) уничтожен. Не остаётся символов стека, чтобы сосчитать \(c\). Формально \(a^n b^n c^n\) не является контекстно-свободным языком (это следует, например, из леммы о накачке для КС-языков).

Решение на TM с одной лентой памяти.

TM использует ленту памяти для хранения \(n\) маркеров \(M\):

1. Состояние \(q_0\) (инициализация): прочитать первый \(a\) и начальный символ \(Z_0\) на ленте памяти. Движение: вход не двигаем, лента памяти вправо (\(\langle S, R \rangle\)). Перейти в \(q_1\).
2. Состояние \(q_1\) (счёт \(a\)): петля: на каждый прочитанный \(a\) записывать \(M\) на память и сдвигать обе головки вправо (\(\langle R, R \rangle\)). Когда на входе \(b\): вход не двигать, головку памяти влево (\(\langle S, L \rangle\)); перейти в \(q_2\).
3. Состояние \(q_2\) (согласование \(b\)): петля: на каждый \(b\) читать \(M\) (он всё ещё на месте) на памяти, вход вправо, память влево (\(\langle R, L \rangle\)). Когда на входе \(c\), а на памяти \(Z_0\): вход не двигать, память вправо (\(\langle S, R \rangle\)); перейти в \(q_3\).
4. Состояние \(q_3\) (согласование \(c\)): петля: на каждый \(c\) читать \(M\) на памяти, обе головки вправо. Когда вход пуст и память пуста: остаться (\(\langle S, S \rangle\)); перейти в \(q_F\) (принимающее).

Ключевая идея: маркеры \(M\) остаются на ленте памяти. Они читаются, но не стираются на фазе подсчёта \(b\) (головка лишь движется назад по ним); они снова доступны на фазе подсчёта \(c\), когда головка снова идёт вперёд.

Ответ: TM распознаёт \(a^n b^n c^n\) именно потому, что память на ленте неразрушительна и позволяет дважды проверить одно и то же \(n\).

4.10. Сравнить NFSA и DFSA для строк, оканчивающихся на 00 (Туториал 9, Пример 1)

Постройте и NFSA, и DFSA, принимающие все двоичные строки, оканчивающиеся на \(00\), над \(\Sigma = \{0, 1\}\).

Показать решение

Ключевая идея: DFSA должна явно отслеживать все «суффиксы в процессе», из‑за чего часто нужно больше состояний. NFSA может «угадать», где начинается финальная \(00\).

Подход DFSA. Машина запоминает два последних прочитанных символа:

• \(q_0\): последний символ был \(1\) (или старт) — петля на \(1\); в \(q_1\) по \(0\).
• \(q_1\): последний символ был \(0\) — в \(q_0\) по \(1\); в \(q_2\) по \(0\).
• \(q_2\) (принимающее): последние два символа были \(00\) — петля на \(0\); в \(q_0\) по \(1\).

DFSA для строк, оканчивающихся на 00

Подход NFSA. Проще — машина «угадывает», где начинается последняя \(00\):

• \(q_0\): петли на \(0, 1\); в \(q_1\) по \(0\) (гипотеза: здесь начало финальной \(00\)).
• \(q_1\): в принимающее \(q_2\) по \(0\).

NFSA для строк, оканчивающихся на 00 (3 состояния, но меньше переходов)

Ответ: здесь у NFSA столько же состояний, но гораздо меньше переходов. Для более длинных шаблонов выигрыш по числу состояний может стать экспоненциальным.

4.11. Перевести NFSA в DFSA построением подмножеств (Туториал 9, Пример 2)

Дан NFSA для строк, оканчивающихся на \(00\) (из примера 4.10 выше), примените построение подмножеств, чтобы получить эквивалентный DFSA.

Таблица переходов NFSA:

\(q\)	\(\delta(q, 0)\)	\(\delta(q, 1)\)
\(\rightarrow q_0\)	\(\{q_0, q_1\}\)	\(\{q_0\}\)
\(q_1\)	\(\{q_2\}\)	\(\emptyset\)
\(*q_2\)	\(\emptyset\)	\(\emptyset\)

Показать решение

Шаг 1. Начать с состояния DFSA \(\{q_0\}\).

Шаг 2. Переходы из \(\{q_0\}\):

• По \(0\): \(\delta(q_0, 0) = \{q_0, q_1\}\) → новое состояние DFSA \(\{q_0, q_1\}\)
• По \(1\): \(\delta(q_0, 1) = \{q_0\}\) → состояние \(\{q_0\}\) (уже известно)

Шаг 3. Переходы из \(\{q_0, q_1\}\):

• По \(0\): \(\delta(q_0, 0) \cup \delta(q_1, 0) = \{q_0, q_1\} \cup \{q_2\} = \{q_0, q_1, q_2\}\) → новое состояние
• По \(1\): \(\delta(q_0, 1) \cup \delta(q_1, 1) = \{q_0\} \cup \emptyset = \{q_0\}\)

Шаг 4. Переходы из \(\{q_0, q_1, q_2\}\):

• По \(0\): \(\{q_0,q_1\} \cup \{q_2\} \cup \emptyset = \{q_0, q_1, q_2\}\)
• По \(1\): \(\{q_0\} \cup \emptyset \cup \emptyset = \{q_0\}\)

Новых состояний нет. Таблица переходов DFSA:

\(q\)	\(\delta_D(q, 0)\)	\(\delta_D(q, 1)\)
\(\rightarrow \{q_0\}\)	\(\{q_0, q_1\}\)	\(\{q_0\}\)
\(\{q_0, q_1\}\)	\(\{q_0, q_1, q_2\}\)	\(\{q_0\}\)
\(*\{q_0, q_1, q_2\}\)	\(\{q_0, q_1, q_2\}\)	\(\{q_0\}\)

\(\{q_0, q_1, q_2\}\) принимающее, так как содержит \(q_2 \in F\).

Ответ: DFSA из 3 состояний, как в примере 4.10 (соответствия \(q_0 \leftrightarrow \{q_0\}\), \(q_1 \leftrightarrow \{q_0, q_1\}\), \(q_2 \leftrightarrow \{q_0, q_1, q_2\}\)).

4.12. Применить конструкцию Томпсона к \((1 \mid 01)^*\) (Туториал 9, Пример 3)

Постройте \(\epsilon\)-NFSA для регулярного выражения \((1 \mid 01)^*\) по конструкции Томпсона, затем упростите, убрав избыточные \(\epsilon\)-переходы.

Показать решение

Шаг 1 — построить \(N(1)\): два состояния \(q_1 \xrightarrow{1} f_1\).

Шаг 2 — построить \(N(0)\) и \(N(1)\) для конкатенации \(01\): \(q_0 \xrightarrow{0} f_0\) и \(q_1' \xrightarrow{1} f_1'\). Соединить \(f_0 \xrightarrow{\epsilon} q_1'\), получая \(N(01)\): \(q_0 \xrightarrow{0} f_0 \xrightarrow{\epsilon} q_1' \xrightarrow{1} f_1'\).

Шаг 3 — объединение \(N(1 \mid 01)\): новые старт \(q_u\) и финал \(f_u\). * \(q_u \xrightarrow{\epsilon} q_1\) (в \(N(1)\)), \(f_1 \xrightarrow{\epsilon} f_u\) * \(q_u \xrightarrow{\epsilon} q_0\) (в \(N(01)\)), \(f_1' \xrightarrow{\epsilon} f_u\)

Шаг 4 — звезда Клини \(N((1 \mid 01)^*)\): новые старт \(q'\) и финал \(f'\). * \(q' \xrightarrow{\epsilon} f'\) (обход для нуля повторов) * \(q' \xrightarrow{\epsilon} q_u\) (вход в объединение) * \(f_u \xrightarrow{\epsilon} q_u\) (цикл назад) * \(f_u \xrightarrow{\epsilon} f'\) (выход)

Шаг 5 — упрощение. После устранения \(\epsilon\) упрощённый NFSA имеет:

• Одно состояние, одновременно старт и принимающее \(q\) (роль \(f'\)).
• \(q \xrightarrow{1} f\) (читаем \(1\) напрямую).
• \(q \xrightarrow{0} m\) (промежуточное), затем \(m \xrightarrow{1} f\) (читаем \(01\)).
• \(f \xrightarrow{\epsilon} q\) (цикл повторов; эквивалентно отождествлению \(f\) с \(q\) после упрощения).

Ответ: упрощённый NFSA принимает любую конкатенацию строк из \(\{1, 01\}\), включая пустую строку. Машина сводится к компактному виду со совпадающими стартом и принятием.